/**必须选择 一种 冰激凌基料baseCosts。
    可以添加 一种或多种 配料toppingCosts，也可以不添加任何配料
    甜点总成本尽可能接近目标价格 target
 * @param {number[]} baseCosts
 * @param {number[]} toppingCosts
 * @param {number} target
 * @return {number} 返回 成本相对较低 的一种
 */
// 深度优先 暴力搜索
var closestCost = function (baseCosts, toppingCosts, target) {
    // 记录所有配料组合的价格
    let total = [];
    function dfs(now, index) {
        if (index == toppingCosts.length) {
            total.push(now);
            return;
        }
        // 每种配料可以选择0-2个
        dfs(now + toppingCosts[index] * 0, index + 1);
        dfs(now + toppingCosts[index] * 1, index + 1);
        dfs(now + toppingCosts[index] * 2, index + 1);
    }
    dfs(0, 0)

    let ret = Infinity;
    for (let i = 0; i < total.length; i++) {
        for (let j = 0; j < baseCosts.length; j++) {
            let tmp = Math.abs(total[i] + baseCosts[j] - target);
            if (tmp < Math.abs(ret - target)) {
                // 差价更低
                ret = total[i] + baseCosts[j];
            } else if (tmp == Math.abs(ret - target) && total[i] + baseCosts[j] < ret) {
                // 差价相同但成本更低
                ret = total[i] + baseCosts[j];
            }
        }
    }
    return ret;
};